/*
 * @lc app=leetcode.cn id=31 lang=csharp
 *
 * [31] 下一个排列
 */

// 1 2 3 4 7 6 5
// 1 2 3 5 4 6 7
// 1 2 3 5 4 7 6
// 1 2 3 5 6 4 7


/*
1) 寻找下降拐点
从右向左找到第一个位置 i，使得 nums[i] < nums[i+1]。
若找不到，说明整个数组单调不增（已是最大排列），直接反转整个数组为升序并返回。
2) 在右侧寻找最小大于 nums[i] 的元素
再从右向左找到第一个位置 j，使得 nums[j] > nums[i]。
3) 交换 nums[i] 与 nums[j]
交换后，前缀到 i 的部分变得更大，但增幅尽量小。
4) 反转后缀
将区间 [i+1, end] 原地反转，使后缀变为最小升序，得到紧邻的下一个字典序排列。

正确性要点
步骤1确保我们从最右端找到可以“变大”的位置 i；
步骤2选择“刚好大一点”的元素 j，保证增量最小；
步骤4把右侧变为最小升序，使总体字典序尽可能靠近原排列的后继。
*/

// @lc code=start
public class Solution {
    public void NextPermutation(int[] nums) {
        int n = nums.Length;
        if (n < 2) return;

        // 1) 找到下降拐点 i
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;

        if (i >= 0) 
        {
            // 2) 从右侧找第一个 > nums[i] 的 j
            int j = n - 1;
            while (nums[j] <= nums[i]) --j;
            // 3) 交换 i, j
            (nums[i], nums[j]) = (nums[j], nums[i]);
        }

        // 4) 反转后缀 [i+1, n-1]
        Reverse(nums, i + 1, n - 1);
    }

    private void Reverse(int[] nums, int left, int right) {
        while (left < right) 
        {
            (nums[left], nums[right]) = (nums[right], nums[left]);
            ++left;
            --right;
        }
    }
}
// @lc code=end

